/*************************************************************************
 * File Name:    Word_Ladder_II.cc
 * Author:       zero91
 * Mail:         jianzhang9102@gmail.com
 * Created Time: Sun 27 Oct 2013 04:17:55 PM CST
 * 
 * Description:  
 |
 |------------------------------------------------------------------------
 | Problem: Word Ladder II
 |
 | Given two words (start and end), and a dictionary, find all shortest
 | transformation sequence(s) from start to end, such that:
 |
 | Only one letter can be changed at a time
 | Each intermediate word must exist in the dictionary
 | For example,
 |
 | Given:
 | start = "hit"
 | end = "cog"
 | dict = ["hot","dot","dog","lot","log"]
 |
 | Return
 | [
 |   ["hit","hot","dot","dog","cog"],
 |   ["hit","hot","lot","log","cog"]
 | ]
 |
 | Note:
 |    All words have the same length.
 |    All words contain only lowercase alphabetic characters.
 |------------------------------------------------------------------------
 |
 ************************************************************************/

#include <iostream>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <map>
#include <set>
#include <functional>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <iomanip>

using namespace std;

class Solution {
private:
    map<string, vector<string> > pre;
    
public:
    vector<vector<string> > findLadders(string start, string end, unordered_set<string> &dict) {
        typedef unordered_set<string>::iterator dict_iter_t;
        map<string, vector<string> > transform;
        
        for (dict_iter_t it = dict.begin(); it != dict.end(); ++it) {
            string t(*it);
            for (size_t i = 0; i < t.size(); ++i) {
                char ch = t[i];
                for (int ic = 'a'; ic <= 'z'; ++ic) {
                    if (ic == ch) continue;
                    t[i] = ic;
                    if (dict.find(t) != dict.end()) {
                        transform[*it].push_back(t);
                    }
                }
                t[i] = ch;
            }
        }
        pre.clear();
        map<string, pair<bool, int> > record;
        
        queue<pair<string, int> > Q;
        Q.push(make_pair(start, 1));
        record[start].first = true;
        record[start].second = 1;
        
        while (!Q.empty()) {
            pair<string, int> t = Q.front();
            Q.pop();
            if (t.first == end) {
                if (!record[end].first) {
                    record[end].first = true;
                    record[end].second = t.second;
                }
                continue;
            }
            
            vector<string> &adj = transform[t.first];
            for (size_t i = 0; i < adj.size(); ++i) {
                if (record[adj[i]].first) {
                    if (record[adj[i]].second == t.second + 1) {
                        pre[adj[i]].push_back(t.first);
                    }
                    continue;
                }
                record[adj[i]].first = true;
                record[adj[i]].second = t.second + 1;
                pre[adj[i]].push_back(t.first);
                Q.push(make_pair(adj[i], t.second + 1));
            }
        }
        vector<vector<string> > ret;
        vector<string> path(1, end);
        dfs(end, start, path, ret);
        return ret;
    }
    
    void dfs(string word, const string &start, vector<string> &path, vector<vector<string> > &ret)
    {
        if (word == start) {
            ret.push_back(vector<string>(path.rbegin(), path.rend()));
            return;
        }
        vector<string> &pre_list = pre[word];
        for (size_t i = 0; i < pre_list.size(); ++i) {
            path.push_back(pre_list[i]);
            dfs(pre_list[i], start, path, ret);
            path.pop_back();
        }
    }
};

